package LeetCode.leetcode76;

import java.util.HashMap;

class Solution {
    public static void main(String[] args) {
        String s = "ADOBECODEBANC";
        String t = "ABC";
        System.out.println(new Solution().minWindow(s, t));
    }
    public String minWindow(String s, String t) {
        HashMap<Character, Integer> needs = new HashMap<>();
        HashMap<Character, Integer> bigMap = new HashMap<>();
        String minRes = "";
        for(char c : t.toCharArray()){
            needs.put(c, needs.getOrDefault(c, 0) + 1);
        }
        for (int j = 0, i = 0; j < s.length(); j++) {
            char c = s.charAt(j);
            bigMap.put(c, bigMap.getOrDefault(c, 0) + 1);
            while (i<=j && mapRealContains(bigMap, needs)) {
                if (minRes.isEmpty()) {
                    minRes = s.substring(i, j+1);
                }else {
                    minRes = s.substring(i, j+1).length() > minRes.length() ? minRes : s.substring(i, j+1);
                }
                char p = s.charAt(i++);
                bigMap.put(p, bigMap.getOrDefault(p, 0) - 1);
            }
        }
        return minRes;
    }
    private boolean mapRealContains(HashMap<Character, Integer> bigMap, HashMap<Character, Integer> smallMap) {
        if (bigMap.size() < smallMap.size()) return false;
        for (char c : smallMap.keySet()) {
            if (!bigMap.containsKey(c)) return false;
            if (bigMap.get(c) < smallMap.get(c)) return false;
        }
        return true;
    }
}